#include "live_var.h"
#include <cassert>
using namespace live_var;
using namespace cfg;
using namespace std;

FuncLiveness LiveVarAnalyzer::Analyze(CFG& cfg)
{
    block_liveness_map.clear();
    var_index_map.clear();
    for (Block& block : cfg.blocks)
    { 
        BlockLiveness block_liveness;
        block_liveness.instrs_liveness.resize(block.instrs.size());
        block_liveness_map[block.label] = move(block_liveness); 
    }
    BuildVarIndex(cfg);
    ComputeInstrUseDef(cfg);
    ComputeBlockUseDef(cfg);
    ComputeBlockInOut(cfg);
    ComputeInstrInOut(cfg);
    func_liveness.block_liveness_map = move(block_liveness_map);
    func_liveness.var_index_map = move(var_index_map);
    return move(func_liveness);
}

void LiveVarAnalyzer::BuildVarIndex(CFG& cfg)
{
    int index = 0;
    for (Block& block : cfg.blocks)
    {
        for (ir::Instruction& instr : block.instrs)
        {
            if (instr.dest != "")
            { var_index_map[instr.dest] = index++; }
        }
    }
    assert(index < MAX_VAR_CNT);
}

void LiveVarAnalyzer::ComputeInstrUseDef(CFG& cfg)
{
    for (Block& block : cfg.blocks)
    {
        BlockLiveness& block_liveness = block_liveness_map[block.label];
        for (size_t i = 0; i < block.instrs.size(); ++i)
        {
            ir::Instruction& instr = block.instrs[i];
            InstrLiveness& instr_liveness = block_liveness.instrs_liveness[i]; 
            for (ir::Operand& src : instr.srcs)
            {
                if (holds_alternative<string>(src))
                {
                    string var_name = get<string>(src);
                    if (var_index_map.count(var_name))
                    {
                        int index = var_index_map[var_name];
                        instr_liveness.use.set(index);
                    }
                }
            }
            if (instr.dest != "")
            { 
                int index = var_index_map[instr.dest];
                instr_liveness.def.set(index);
            }
        }
    }
}

void LiveVarAnalyzer::ComputeBlockUseDef(CFG& cfg)
{
    for (Block& block : cfg.blocks)
    {
        BlockLiveness& block_liveness = block_liveness_map[block.label];
        for (InstrLiveness& instr_liveness : block_liveness.instrs_liveness)
        {
            block_liveness.use |= instr_liveness.use;
            block_liveness.def |= instr_liveness.def;
        }
    }
}

void LiveVarAnalyzer::ComputeBlockInOut(CFG& cfg)
{
    bool changed = true;
    while (changed)
    {
        changed = false;
        for (Block& block : cfg.blocks)
        {
            BlockLiveness& block_liveness = block_liveness_map[block.label];
            bitset<MAX_VAR_CNT> old_out = block_liveness.out;
            bitset<MAX_VAR_CNT> old_in = block_liveness.in;
            block_liveness.out.reset();
            // out = ∪ in
            for (Block* succ : block.succs)
            { block_liveness.out |= block_liveness_map[succ->label].in; }
            // in = use ∪ (out - def)
            block_liveness.in = block_liveness.use 
                | (block_liveness.out & ~block_liveness.def);
            if (block_liveness.out != old_out || block_liveness.in != old_in)
            { changed = true; }
        }
    }
}

void LiveVarAnalyzer::ComputeInstrInOut(CFG& cfg)
{
    for (Block& block : cfg.blocks)
    {
        BlockLiveness& block_liveness = block_liveness_map[block.label];
        vector<InstrLiveness>& instrs_liveness = 
            block_liveness.instrs_liveness;
        instrs_liveness.back().out = block_liveness.out;
        for (int i = instrs_liveness.size() - 1; i >= 0; --i)
        {
            // in = use ∪ (out - def)
            instrs_liveness[i].in = instrs_liveness[i].use
                | (instrs_liveness[i].out & ~instrs_liveness[i].def);
            if (i > 0) 
            {instrs_liveness[i-1].out = instrs_liveness[i].in; }
        }
    }
}